This invention relates to methods and means for scheduling tasks performed by parallel processors, and particularly to concurrent execution of operations in a number of functional units in cooperation with an assignment manager.
Traditional data processing systems execute a sequence of instructions one at a time. To increase the execution speed of computers, multiple processors are used to perform parallel processing of primitive operations, or tasks. Such parallelism often requires substantially more space (memory) than sequential operations.
Many parallel programming languages allow for parallel processing in separate functional units. The goal of these languages is to have the user expose the full parallelism and have the language implementation schedule the parallelism onto processors. Costs of such operations can be measured abstractly in terms of the total number of operations executed by the program, i.e. the xe2x80x9cworkxe2x80x9d, and the length of the longest sequence of dependencies, the i.e. the xe2x80x9cdepthxe2x80x9d. Performance anomalies in such arrangements are often common. Heuristics used in the implementation often fail. Such systems do not necessarily offer good performance, both in terms of time and space.
The aforementioned application Ser. No. 08/502,625, filed Jul. 14, 1995, involved determining sequential ordering of tasks for processing, assigning priorities to the tasks available on the basis of the sequential ordering, selecting a number of tasks greater than a total number of available processing elements from all available tasks having the highest priorities, partitioning the selected tasks into a number of groups equal to the available number of parallel processing elements, and processing the tasks in the parallel processing elements.
The processing elements in the latter application have buffers and operate in synchronism. An assignment manager pushes tasks into the buffers of each processing element.
In an embodiment of the invention, the assignment manager makes live tasks available and the processing elements extract the tasks and keep executing the tasks and upon reaching a criterion (time, memory etc.) each element feeds information back to the assignment manager and extracts more tasks. The assignment manager establishes the criterion and determines task priorities on the basis of a sequential schedule independent of the execution of the extracted tasks in the processing elements.
The various aspects of the invention are pointed out in the claims. Other objects and advantages of the invention will become evident when read in light of the accompanying drawings.